# longest increasing subsequence
def LIS(array):
    longest=[]
    for i in range(len(array)-1,0,-1):
        top=array[i]
        subarray=[top]
        for j in range(i-1,-1,-1):
            if array[j]<top:
                subarray.append(array[j])
                top=array[j]
        if len(subarray)>len(longest):
            longest=subarray
    return len(sorted(longest))

def LIS2(array):
    longest=[]
    for i in range(len(array)-1,0,-1):
        top=array[i]
        subarray=[top]
        for j in range(i-1,-1,-1):
            if array[j]<top:
                subarray.append(array[j])
                top=array[j]
        if len(subarray)>len(longest):
            longest=subarray
        if len(subarray)>=i:
            break
    return len(sorted(longest))

# minimum path sum
from itertools import permutations
def MPS(grid):
    def move_route(grid):
        m=len(grid)-1
        n=len(grid[0])-1
        pool=[0]*m+[1]*n
        routes=set(list(permutations(pool,len(pool))))
        return sorted(list(routes))
    results={}
    routes=move_route(grid)
    for route in routes:
        x,y=0,0
        result=grid[y][x]
        for n in route:
            if n == 0:
                y+=1
            if n == 1:
                x+=1
            result+=grid[y][x]
        results[str(route)]=result
    best_route=routes[0]
    for route in results:
        if(results[route])<results[str(best_route)]:
            best_route=eval(route)
    return best_route

# stock trading
def maxprofit(prices):
    best=0
    n=len(prices)-1
    head=prices[0]
    for i in range(n):
        purchase=prices[i]
        if purchase >= head:
            continue
        else:
            head=purchase
        profit=max(prices[i:])-purchase
        if profit > best:
            best=profit
    return best

# theft plan
def rob(money):
    n=len(money)
    F=[0]*n
    M=[0]*n
    F[0]=money[0]
    M[0]=0
    for i in range(1,n):
        F[i]=M[i-1]+money[i]
        M[i]=max(F[i-1],M[i-1])
    return max(F[-1],M[-1])

# different routes
def count_routes(grid,m,n):
    P=[]
    for i in range(m):
        P.append([1]*n)
    for i in range(1,m):
        for j in range(1,n):
            P[i][j]=P[i-1][j]+P[i][j-1]
    return P[-1][-1]

# longest common subsequence
def LCS(text1,text2):
    P=[]
    m=len(text1)
    n=len(text2)
    for i in range(m):
        P.append([0]*n)
    for j in range(n):
        if text2[j] != text1[0]:
            P[0][j]=0
        elif j == 0:
            P[0][j]=1
        else:
            P[0][j]=max(P[0][j-1],1)
    for i in range(m):
        if text1[i] != text2[0]:
            P[i][0]=0
        elif i== 0:
            P[i][0]=1
        else:
            P[i][0]=max(P[i-1][0],1)
    for i in range(1,m):
        for j in range(1,n):
            if text1[i] == text2[j]:
                P[i][j]=P[i-1][j-1]+1
            else:
                P[i][j]=max(P[i-1][j],P[i][j-1])
    return P[-1][-1]
